On désigne par "tri" l'opération consistant à ordonner un ensemble d'éléments en fonction de clés sur lesquelles est définie une relation d'ordre.
Les algorithmes de tri ont une grande importance pratique. Ils sont fondamentaux dans certains domaines, comme l'informatique de gestion où l'on tri de manière quasi-systématique des données avant de les utiliser.
L'étude du tri est également intéressante en elle-même car il s'agit sans doute du domaine de l'algorithmique qui a été le plus étudié et qui a conduit à des résultats remarquables sur la construction d'algorithmes et l'étude de leur complexité.
Tris élémentaires |
Tris avancés |
Le tri par insertion. |
Le tri fusion. |
Le tri par sélection. |
Le tri rapide. |
Le tri bulle. |
|
Le tri Shell. |
|
Le tri indirect. |
|
Le tri par insertion correspond a la comparaison des personnes entre elles et ensuite de les classé par grandeur. Pour ce tri on utilise une comparaison de l’ensemble des participants.
Le principe du tri par sélection/échange (ou tri par extraction) est d'aller chercher le plus petit élément du vecteur pour le mettre en premier, puis de repartir du second élément et d'aller chercher le deuxième plus petit élément du vecteur pour le mettre en second, etc...
Le principe du tri bulle (bubble sort) est de comparer deux à deux les éléments e1 et e2 consécutifs d'un tableau et d'effecteur une permutation si e1 > e2. On continue de trier jusqu'à ce qu'il n'y ait plus de permutation. (Méthode que Samir a utilisé mors du Prosit)
Le principe du tri Shell consiste a trié les variable d’abord deux par deux avec un écart de h (nobre choisi par l’utilisateur). Lorsque ce tri est fini on réutilise le tri par insertion. L’utilité de cette méthode est que lors du pire des cas c'est-à-dire où les variable sont classées dans l’ordre décroissant alors que l’on veut un ordre croissant le tri par insertion va être très long alors que le tri Shell va accéléré sensiblement ce tri.
Le tri indirect utilise un tableau auxiliaire qui indique, pour chaque élément du tableau à trier, le rang que celui-ci devrait occuper dans le tableau trié. Le tri se fait ensuite par l'intermédiaire de cet index.
Le principe du tri fusion est :
Le tri maximier (aussi appelée «tri par tas» ou «heapsort» ou «tri de Williams») est basée sur la notion de tas. Un tas est un arbre binaire parfait tel que l’information contenue dans tout nœud est supérieure à celle contenue dans ses fils. La méthode du tri par tas comporte deux étapes :
POUR i VARIANT DE 2 A n FAIRE
INSERER a[i] à sa place dans a[1:i-1];
FIN PROCEDURE
PRODECURE Tri_Selection (Tableau a[1:n])
VARIABLE indice_max : ENTIER;
POUR i VARIANT DE 1 A n-1 FAIRE
indice_max <- i;
POUR j VARIANT DE i+1 A N FAIRE
SI a[j]<max ALORS indice_max <- j;
FIN POUR
echanger a[i] et a[indice_max];
FIN POUR
FIN PROCEDURE
PRODECURE Tri_bulle (Tableau a[1:n])
VARIABLE permut : Booleen;
REPETER
permut = FAUX
POUR i VARIANT DE 1 à N-1 FAIRE
SI a[i] > a[i+1] ALORS
echanger a[i] et a[i+1]
permut = VRAI
FIN SI
FIN POUR
TANT QUE permut = VRAI
FIN PROCEDURE
PROCEDURE Tri_Shell (Tableau a [1: n] )
POUR i VARIANT DE h en h FAIRE
SI a[hi+1] = a[3hi+1] ALORS
echanger a[i+1] et a[i]
permut = VRAI
FIN SI
FIN POUR
TANT QUE permut = VRAI
FIN PROCEDURE
fusion(tableau T,entier premier1,entier dernier1,entier dernier2)
debut
tableau Tbis
entier premier2, compteur1, compteur2, i
premier2<-dernier1+1
compteur1<-premier1
compteur2<-premier2
taille(T)<-(dernier1-premier1+1) //taille du premier sous tableau
//on recopie dans T les éléments du premier sous tableau
pour i=premier1 à dernier1 faire
Tbis(i-premier1)<-T(i)
fin pour
//on fusionne ensuite les deux sous tableaux
pour i=premier1 à dernier2 faire
si compteur1=premier2 alors //tous les éléments du premier sous tableau ont été utilisés
arret pour //tous les éléments sont donc classés
sinon si compteur2=(dernier2+1) alors //tous les éléments du second sous tableau ont été utilisés
T(i)=Tbis(compteur1-premier1) //on recopie à la fin du tableau les éléments du premier sous tableau
compteur1<-compteur1+1
sinon si Tbis(compteur1-premier1)<T(compteur2) alors //l'élément du premier sous tableau est le plus petit
T(i)<-Tbis(compteur1-premier1) //on ajoute un élémnt du premier sous tableau
compteur1<-compteur1+1 //on progresse dans le premier sous tableau
sinon //c'est l'élément du second sous tableau qui est le plus petit
T(i)<-T(compteur2) //on recopie cette élément à la suite du tableau
compteur2<-compteur2+1 //on progresse dans le second tableau
fin si
fin pour
fin
tri_fusion_bis(tableau T,entier premier,entier dernier)
debut
entier milieu;
si premier<>dernier alors
//si l'indice du premier et du dernier élément à traiter
//est différent (condition d'arret de l'algorithme)
milieu<-(premier+dernier)/2
tri_fusion_bis(T,premier,milieu) //tri de la premiére moitiée du sous tableau
tri_fusion_bis(T,milieu+1,dernier) //tri de la seconde moitiée du sous tableau
fusion(T,premier,milieu,dernier) //fusion des deux sous moitiées
fin si
fin
tri_fusion(tableau T)
debut
entier longueur
longueur<-taille(T)
si longueur>0 alors
tri_fusion_bis(T,0,longueur-1)
fin si
fin
partition(tableau T, entier premier, entier dernier)
debut
entier compteur, pivot, i
compteur<-premier
pivot<-T(premier)
pour i=deb+1 à dernier faire
si T(i)<pivot alors //si l'élément est inférieur au pivot
compteur<-compteur+1 //on incrémente le compteur (modification de la place finale du pivot)
echanger(T,compteur,i) //on place l'élément à la position finale du pivot
fin si
fin pour
echanger(T,compteur,premier) //on place le pivot à sa place
retourner(compteur) //on renvoie la position finale du pivot
fin
tri_rapide_bis(tableau T, entier premier, entier dernier)
debut
entier pivot
si premier<dernier alors //condition d'arret de la récursivité
pivot<-partition(T,premier,dernier) //partition du tableau en 2
tri_rapide_bis(T,premier,pivot-1) //tri de la premiére partition
tri_rapide_bis(T,pivot+1,dernier) //tri de la seconde partition
fin si
fin
tri_rapide(tableau T)
debut
tri_rapide_bis(T,0,taille(T)-1)) //tri du tableau entier
fin